package 剑指offer_leetcode;

import java.util.ArrayList;

/**
 * JZ74和为S的连续正数序列
 */
public class 剑指Offer57_II_和为s的连续正数序列 {
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> res = new ArrayList<int[]>();
        int sum1 = 0;
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int up = (target - 1) / 2;
        //枚举左区间
        for(int i = 1; i <= up; i++){
            //从左区间往后依次连续累加
            for(int j = i; ;j++){
                sum1+=j;
                //大于目标和则跳出该左区间
                if(sum1 > target) {
                    sum1 = 0;
                    break;
                }else if(sum1==target){
                    //等于则找到了
                    sum1 = 0;
                    int[] temp = new int[j-i+1];
                    //记录线序的数字
                    for(int k = i; k <= j; k++)
                        temp[k-i] =  k;
                    res.add(temp);
                    break;
                }
            }
        }
        if(res.size()==0)
            return new int[0][0];
        return res.toArray(new int[res.size()][]);

    }
}
